﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0176_MinRemoveToMakeValid : IAlgorithm
    {
        // 1249. 移除无效的括号

        // 给你一个由 '('、')' 和小写字母组成的字符串 s。

        //  你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
        //  请返回任意一个合法字符串。

        // 有效「括号字符串」应当符合以下 任意一条 要求：
        //  空字符串或只包含小写字母的字符串
        //  可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」
        //  可以被写作(A) 的字符串，其中 A 是一个有效的「括号字符串」


        public void Test()
        {
            // 算法参数定义
            string s = "lee(t(c)o)de)";
            // 算法执行与打印
            Console.WriteLine(MinRemoveToMakeValid(s));
        }

        // 算法
        public string MinRemoveToMakeValid(string s)
        {
            var sb = new StringBuilder();
            var stack = new Stack<int>();
            foreach (var c in s)
            {
                if (c == ')')
                    if (stack.Count == 0) continue;
                    else stack.Pop();
                if (c == '(')
                    stack.Push(sb.Length);
                sb.Append(c);
            }

            while (stack.Count > 0)
                sb.Remove(stack.Pop(), 1);

            return sb.ToString();
        }
    }
}
